// ??? // Where the Wild Things Are // Author: Constantine Sokol // Complexity : O( N + Q * log N ) // Expected Verdict: AC #include #include #include using namespace std; const int maxn = 100000 + 5; int n, q, x[ maxn ], y[ maxn ]; long long sq( int a, int b, int c ) { long long x1 = x[b] - x[a]; long long y1 = y[b] - y[a]; long long x2 = x[c] - x[a]; long long y2 = y[c] - y[a]; long long square = x1 * y2 - y1 * x2; return max( square, -square ); } int query( int a, int b, long long s, int l, int r ) { assert( l <= r ); int mem_l = l; int mem_r = r; while ( r - l >= 3 ) { int m1 = l + ( r - l + 1 ) / 3; int m2 = r - ( r - l + 1 ) / 3; if ( sq( a, b, m1 ) < sq( a, b, m2 ) ) l = m1; else r = m2; } int pos = l; for ( int i = l; i <= r; i++ ) if ( sq( a, b, i ) > sq( a, b, pos ) ) pos = i; if ( sq( a, b, pos ) < s ) return 0; l = mem_l; r = pos - 1; int left_bound = pos; while ( l <= r ) { int x = (l + r) / 2; if ( sq( a, b, x ) >= s ) { left_bound = min( left_bound, x ); r = x - 1; } else l = x + 1; } l = pos + 1; r = mem_r; int right_bound = pos; while ( l <= r ) { int x = (l + r) / 2; if ( sq( a, b, x ) >= s ) { right_bound = max( right_bound, x ); l = x + 1; } else r = x - 1; } return right_bound - left_bound + 1; } int main() { scanf("%d%d", &n, &q); for ( int i = 1; i <= n; i++ ) scanf("%d%d", &x[i], &y[i]); for ( int it = 1; it <= q; it++ ) { int l, r; long long s; scanf("%d%d%lld", &l, &r, &s); s *= 2; assert( l != r ); if ( l > r ) swap( l, r ); printf("%d\n", query( l, r, s, l, r ) + query( l, r, s, r, n ) + query( l, r, s, 1, l ) ); } return 0; }